package baseclass.b_stackQueue;

import java.util.Stack;

/**
 * 用栈实现双端队列。
 * 基于用栈实现单向队列，
 * pop的时候发生update:
 * 1、pop必须为空，push才能向pop倒入
 * 2、push必须一次性倒完
 * <p>
 * 双端队列就是，可以从两侧插入，从两侧移除
 * <p>
 * 修改点：
 * 譬如pushStack分别进入1,2,3,4 ，此时若发生poll,那么
 * 就要将4,3,2,1依次像popStack倒入，然后出栈1.
 * 然后popStack剩下2，3，4
 * <p>
 * 如果此时addFirst,直接插入到popStack即可，比如插入8
 * popStack = 8,2,3,4
 * <p>
 * 如果此时removeLast，那么同样把popStack倒入到pushStack，
 * 此时pushStack是4,3,2然后移除4
 * <p>
 * <p>
 * 总结：用栈实现双端队列
 * <p>
 * 如果是addLast，那么就是正常push操作。
 * 如果是removeFirst，那么就是正常pop操作。
 * 如果addFirst，那么就把元素进入到popStack最顶端
 * 如果是removeLast，那么就发生pop向push倒入，然后返回push栈顶
 *
 * @date 2020/2/27 18:07
 */
public class Code06_StackToDeque {
    private Stack<Integer> pushStack;
    private Stack<Integer> popStack;

    public Code06_StackToDeque() {
        this.pushStack = new Stack<>();
        this.popStack = new Stack<>();
    }
    public void addLast(int e){
        //入栈操作
        pushStack.push(e);
    }

    public void addFirst(int e){
        //只要加入到popStack栈顶，表示最新元素
        popStack.push(e);
    }
    //出队列，最早的元素。发生pushStack向popStack 倒入的过程
    public int pollFirst(){
        updateFromPushToPop();
        return popStack.pop();
    }
    private void updateFromPushToPop(){

        if(!popStack.isEmpty()) return;
        System.out.println("dao1");
        while (!pushStack.isEmpty()){
            popStack.push(pushStack.pop());
        }
        if(popStack.isEmpty()) return;
    }

    //出队列，最晚插入的元素，就是刚刚pop进去的元素。发生popStack向pushStack倒入
    public int pollLast(){
        updateFromPopToPush();
        return pushStack.pop();
    }

    private void updateFromPopToPush() {
        if(!pushStack.isEmpty()) return;
        System.out.println("dao2");
        while (!popStack.isEmpty()){
            pushStack.push(popStack.pop());
        }
    }

    public static void main(String[] args) {
        Code06_StackToDeque deque = new Code06_StackToDeque();
        deque.addLast(1);
        deque.addLast(2);
        deque.addLast(3);
        deque.addLast(4);
        System.out.println(deque.pollFirst());
        System.out.println(deque.pollFirst());
        deque.addFirst(5);
        System.out.println(deque.pollLast());
    }
}
